package com.leetcode.algorithm.y22.m09.w2;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 735. 行星碰撞
 * 
 * https://leetcode.cn/problems/asteroid-collision/
 * 
 * @author jie.deng
 *
 */
class Question0735Solution01 {

	public int[] asteroidCollision(int[] asteroids) {
		int len = asteroids.length;
		Deque<Integer> stack = new ArrayDeque<>();
		for (int i = 0; i < len; i++) {
			if (stack.isEmpty() || asteroids[i] > 0 || stack.peekLast().intValue() < 0) {
				// a.空
				// b.当前行星向右移动
				// c.当前行星向左移动 && 前一个行星向左移动
				stack.offerLast(asteroids[i]);
				continue;
			}

			// d.当前行星向左移动 && 前一个行星向右移动
			boolean flag = true;
			while (!stack.isEmpty()) {
				int prev = stack.peekLast().intValue();
				if (prev < 0) {
					break;
				}
				if (prev > -asteroids[i]) {
					flag = false;
					break;
				} else if (prev == -asteroids[i]) {
					flag = false;
					stack.pollLast();
					break;
				} else {
					stack.pollLast();
				}
			}
			if (flag) {
				stack.offerLast(asteroids[i]);
			}
		}

		int[] ans = new int[stack.size()];
		int idx = 0;
		while (!stack.isEmpty()) {
			ans[idx++] = stack.pollFirst().intValue();
		}
		return ans;
	}

}